The problem can be found at the following link: Question Link
To find the greatest value node in the Binary Search Tree (BST) that is smaller than or equal to a given value x, you can follow these steps:
- Initialize a variable floorValue to -1. This variable will store the floor value as we traverse the BST.
- Start at the root of the BST.
- Traverse the BST while comparing the values of nodes with x and updating floorValue accordingly. Use the following rules:
- If the current node's data is equal to x, return x as the floor value because you've found an exact match.
- If the current node's data is less than x, update floorValue to the current node's data, as it's a potential floor value, and move to the right subtree because you are looking for a greater value.
- If the current node's data is greater than x, move to the left subtree because you are looking for a smaller value.
- Continue this process until you have traversed the entire BST.
- Return floorValue as the final result.
-
Time Complexity: The time complexity of this algorithm is
O(H)
, whereH
is the height of the BST. In the best case, when the tree is balanced, the height H is log(N). So, the time complexity can vary fromO(N)
in the worst case toO(log(N))
in the best case. -
Space Complexity: The space complexity of this algorithm is
O(1)
class Solution{
public:
int floor(Node* root, int x) {
// Code here
int floorValue = -1;
while (root != nullptr)
{
if (root->data == x)
{
return x;
}
else if (root->data < x)
{
floorValue = root->data;
root = root->right;
}
else
{
root = root->left;
}
}
return floorValue;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.